//给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。
//
// 注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。
//
//
//
// 示例 1：
//
//
//输入：n = 12
//输出：21
//
//
// 示例 2：
//
//
//输入：n = 21
//输出：-1
//
//
//
//
// 提示：
//
//
// 1 <= n <= 2³¹ - 1
//
// Related Topics 数学 双指针 字符串 👍 183 👎 0

package leetcode.editor.cn;

@SuppressWarnings("all")
//Java：下一个更大元素 III
class 下一个更大元素3 {
    public static void main(String[] args) {
        Solution solution = new 下一个更大元素3().new Solution();
        // TO TEST
        System.out.println(solution.nextGreaterElement(12));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int nextGreaterElement(int n) {

            if (n <= 11)
                return -1;
            char[] chars = String.valueOf(n).toCharArray();
            int i, j;


            for (i = chars.length - 2; i >= 0; i--) {
                if (chars[i] < chars[i + 1])
                    break;
            }

            if (i >= 0) {
                for (j = chars.length - 1; j >= 0; j--) {
                    if (chars[j] > chars[i])
                        break;
                }
                if (i != j)
                    swap(chars, i, j);
            }

            if (i + 1 < chars.length)
                reverse(chars, i + 1);

            int sum = chars[0] - '0';
            for (int k = 1; k < chars.length; k++) {
                sum = sum * 10 + chars[k] - '0';
            }

            if (sum > n)
                return sum;

            return -1;
        }

        private void reverse(char[] chars, int start) {
            int end = chars.length - 1;

            while (start < end) {
                swap(chars, start++, end--);
            }

        }

        private void swap(char[] arr, int index1, int index2) {
            int temp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = (char) temp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
